ftp.mactech.com 2010/ftp.mactech.com.tar/ftp.mactech.com/machack/Hacks97/WarriorsProgress.sit/Warrior’s Progress/source code/Source/Libraries/Trees/RedBlackTree.cp

Text File | 1997-06-28 | 5KB | 231 lines

// RedBlackTree.cp

#ifndef RedBlackTree_h
#include "RedBlackTree.h"
#endif
#ifndef RedBlackNode_h
#include "RedBlackNode.h"
#endif

RedBlackTree::RedBlackTree()
  : blackHeight( 0 )
  {
  }

RedBlackTree::~RedBlackTree()
  {
    Assert( blackHeight == 0 );
  }

RedBlackNode *RedBlackTree::DownCast( TreeNode *n )
  {
    return static_cast< RedBlackNode* >( n );
  }

const RedBlackNode *RedBlackTree::DownCast( const TreeNode *n )
  {
    return static_cast< const RedBlackNode* >( n );
  }

void RedBlackTree::Add( RedBlackNode& newNode, AtRoot )
  {
    Assert( newNode.IsRed() );
    Tree::Add( newNode, atRoot );
    Assert( blackHeight == 0 );
  }

void RedBlackTree::Add( RedBlackNode& newNode,
                                Before,
                                RedBlackNode& next )
  {
    Assert( newNode.IsRed() );
    Assert( !next.HasLeftChild() );
    Assert( next.IsBlack() || !next.HasRightChild() );
    Assert( !next.HasRightChild() || next.Right()->IsRed() );
    Assert( !next.HasRightChild() || next.Right()->IsLeaf() );

    Tree::Add( newNode, before, next );
    FixRedChain( newNode );
  }

void RedBlackTree::Add( RedBlackNode& newNode,
                                After,
                                RedBlackNode& previous )
  {
    Assert( newNode.IsRed() );
    Assert( !previous.HasRightChild() );
    Assert( previous.IsBlack() || previous.IsLeaf() );
    Assert( !previous.HasLeftChild() || previous.Left()->IsRed() );
    Assert( !previous.HasLeftChild() || previous.Left()->IsLeaf() );

    Tree::Add( newNode, after, previous );
    FixRedChain( newNode );
  }

void RedBlackTree::Remove( RedBlackNode& toRemove )
  {
    if ( toRemove.HasLeftChild() )
      {
        RedBlackNode *previous = toRemove.Previous();
        Assert( previous != 0 );
        toRemove.SwapWith( *previous );

        if ( toRemove.HasLeftChild() )
          {
            Assert( toRemove.Left()->IsRed() );
            toRemove.Left()->RotateUp();
          }
      }
     else if ( toRemove.HasRightChild() )
      {
        RedBlackNode *next = toRemove.Next();
        Assert( next != 0 );
        toRemove.SwapWith( *next );

        if ( toRemove.HasRightChild() )
          {
            Assert( toRemove.Right()->IsRed() );
            toRemove.Right()->RotateUp();
          }
      }

    Assert( toRemove.IsLeaf() );
    Redden( toRemove );
    Tree::Remove( toRemove );
  }

void RedBlackTree::RemoveAll()
  {
    RedBlackNode *first = First();
    while ( first != 0 )
      {
        Assert( !first->HasLeftChild() );

        if ( first->HasRightChild() )
            Remove( *first->Right() );

        Assert( !first->HasRightChild() );

        RedBlackNode *next = first->Parent();
        Remove( *first );
        first = next;
      }
  }

void RedBlackTree::FixRedChain( RedBlackNode& toFix )
  {
    Assert( &toFix.Owner() == this );

    RedBlackNode *lower = &toFix;

    while ( true )
      {
        Assert( lower != 0 );
        Assert( lower->IsRed() );

        RedBlackNode *upper = lower->Parent();

        if ( upper == 0 || upper->IsBlack() )
            break;

        if ( upper->IsRoot() )
          {
            upper->red = false;
            blackHeight++;
            break;
          }

        RedBlackNode *sibling = upper->Sibling();

        if ( sibling == 0 || sibling->IsBlack() )
          {
            if ( lower->IsLeftChild() != upper->IsLeftChild() )
              {
                lower->RotateUp();
                lower->RotateUp();
              }
             else
                upper->RotateUp();
            break;
          }

        lower = upper->Parent();
        lower->Raise();
      }
  }

void RedBlackTree::Redden( RedBlackNode& toRedden )
  {
    Assert( &toRedden.Owner() == this );
    Assert( toRedden.RedChildren() == 0 );

    if ( toRedden.IsRed() )
        return;

    // Try changing the root color
      {
        if ( toRedden.IsRoot() )
          {
            Assert( blackHeight > 0 );
            toRedden.red = true;
            blackHeight--;
            return;
          }
      }

    RedBlackNode *sibling = toRedden.Sibling();
    Assert( sibling != 0 );
    if ( sibling->IsRed() )
      {
        sibling->RotateUp();
        sibling = toRedden.Sibling();
        Assert( sibling != 0 );
      }
    Assert( !sibling->IsRed() );

    // If we have a red left niece, borrow from our sibling
      {
        RedBlackNode *leftNiece = sibling->Left();
        if ( leftNiece != 0 && leftNiece->IsRed() )
          {
            if ( sibling->IsLeftChild() )
                sibling->RotateUp();
             else
              {
                leftNiece->RotateUp();
                leftNiece->RotateUp();
              }
            Assert( toRedden.IsRed() );
            return;
          }
      }

    // If we have a red right niece, borrow from our sibling
      {
        RedBlackNode *rightNiece = sibling->Right();
        if ( rightNiece != 0 && rightNiece->IsRed() )
          {
            if ( sibling->IsRightChild() )
                sibling->RotateUp();
             else
              {
                rightNiece->RotateUp();
                rightNiece->RotateUp();
              }
            Assert( toRedden.IsRed() );
            return;
          }
      }

    Redden( *toRedden.Parent() );
    toRedden.Parent()->Lower();
  }

bool RedBlackTree::Valid() const
  {
    if ( IsEmpty() )
        return blackHeight == 0;

    return Root()->Valid( blackHeight );
  }